/*
 *  HeapPQueue.h
 *  project2
 *
 *  Created by Maria Piao on 09-10-11.
 *  Copyright 2009 __MyCompanyName__. All rights reserved.
 *
 */

#ifndef _HEAPPQUEUE_H
#define _HEAPPQUEUE_H

#include <iostream>
#include <vector>
#include "PQueue.h"

using namespace std;

template <class Object, class Compare>
class HeapPQueue: public PriorityQueue<Object, Compare> {
public:
	HeapPQueue(int arity);              // Constructor specifying degree of the tree
	~HeapPQueue();						// Destructor
	
	// Const functions
	
	int getNumberOfElements();
	bool isEmpty() const;               // True iff the pqueue is empty
	const Object & findMin() const;     // Returns unchangeable reference to

	void insert(const Object & x);      // Inserts a copy of x into the pqueue
	void deleteMin();                   // Deletes the minimum element from the pqueue 
	void deleteMin(Object & minItem);   // Deletes the minimum element from the pqueue and puts a copy of it into minItem.
	void makeEmpty();                   // Deletes all elements from the pqueue.
	void printHeap();
	void printTypeName();
	
protected:
	vector<Object> heap;				//The Tree, implemented using std::vector
	Compare comp;						//The comparator, there be unique to the maze
	int arity;							//Indicate the degree of the tree, if not specified, default to 2
	void percolateUpLastElement();		//Make sure the last element in the tree has a valid parent
	void percolateUp(int index);		//Make sure the element at index is in its proper place
	void percolateDownRoot();			//Make sure the root is at the right place
	void percolateDown(int index);		//Make sure the element at index is in its proper place has valid children
	bool shouldSwap (Object parent, Object child); //Is the child bigger than the parent (assuming max tree)
	void swap (int index1, int index2);				//switch the elements and index 1 and index2
};


// Suck in the implementation code to make templates work.
#include "HeapPQueue.cpp"


#endif
